package _05_二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class _144_二叉树的前序遍历复习 {

    // 二叉树的前序遍历，非递归, 遍历到的节点输出，右节点入栈
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            if (root != null) {
                // 遍历到获取的节点
                results.add(root.val);
                // 右节点入栈
                if (root.right != null) {
                    stack.push(root.right);
                }
                root = root.left;
            } else {
                // 出栈右节点
                if (!stack.isEmpty()) {
                    // 当前出栈节点，当做根节点处理
                    root = stack.pop();
                } else {
                    break;
                }
            }
        }
        return results;
    }

}
